#include<iostream>
#include<vector>
using namespace std;
#define N 5

void dfs(vector<int>&a, int sum, vector<char> &x, int i)
{
	// 到达一个叶子结点(可能解)
	if (i==N)
	{		// 找到一个可行解
		if (sum==5)
		{
			// 输出解
			printf("  %d", a[0]);
			for (int j=1; j<N; j++)
			{
				printf("%c",x[j]);
				printf("%d",a[j]);
			}
			printf("=5\n");
		}
	}
	
	// 未到达叶子结点
	else
	{
		// 位置i插入'+'
		x[i]='+';
		sum += a[i]; // 计算结果
		dfs(a, sum, x, i+1); // 继续搜索
		sum -=a [i]; // 回溯

		// 位置i插入'-'
		x[i]='-';
		sum -= a[i]; // 计算结果
		dfs(a, sum, x, i+1); // 继续搜索
		sum += a[i];	 // 回溯
	}
}

// 求解算法
void solve(vector<int>&a)
{
	// 定义解向量
	vector<char> x(a.size());
	
	// i从1开始 
	dfs(a, a[0], x, 1);
}

int main()
{
	// 初始化数组
	vector<int> a={1, 2, 3, 4, 5};
	
	// 输出所有表达式
	printf("求解结果\n");
	solve(a); 
	return 0;
}
